package 简单.动态规划;

/**
 * 给一个数组，类型为int类型，将数组之和。
 * 1，定义子问题
 * 累加到i个值的和是多少
 * 2，写出子问题的递推关系
 * 第i个值等于，i-1的和加上nums[i]
 * dp[i]=dp[i-1]+nums[i]
 * 3，确定顺序
 * 从首到尾
 * 4，空间优化
 * 第i个值，只与i-1的值有关
 */
public class 累加求和 {

    public static void main(String[] args) {

        int[] nums = {1, 2, 4, -1};
        int sum = efficientSum(nums);
        System.out.println(sum);
    }

    //动态规划
    public static int sum(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int[] dp = new int[len];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = dp[i - 1] + nums[i];
        }
        return dp[len - 1];
    }

    //空间优化
    public static int efficientSum(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int pre1 = 0;
        int cur;
        for (int num : nums) {
            cur = pre1 + num;
            pre1 = cur;
        }
        return pre1;
    }

}
